package algorithm.leetcode.simple;

/*
 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 */

/**
 * @author
 * @version 1.0
 * @date 2020/9/22
 */
public class Question29 {

    public static void main(String[] args) {

        Question29 question = new Question29();
        long res = question.divide(2147483647, 2);
        System.out.println(res);
    }

    public long divide(int dividend, int divisor) {
        if (dividend == 0) {
            // 如果被除数为0 返回0
            return 0;
        }
        if (divisor == 1) {
            // 如果除数为1 返回被除数本身
            return dividend;
        }
        if (divisor == -1) {
            // 如果除数为-1 返回相反数
            if (dividend > Integer.MIN_VALUE) {
                return - dividend;
            }
            // 如果被除数比题目要求的数还小 返回最大数
            return Integer.MAX_VALUE;
        }

        long a = dividend;
        long b = divisor;

        // 定义符号标志位 默认为正数
        int sign = 1;

        if ((a > 0 && b < 0) || (a < 0 && b > 0)) {
            // 只要有一个为负数 符号标志位更改为负数
            sign = -1;
        }

        // 全部使用正数接下来操作
        a = a > 0 ? a : -a;
        b = b > 0 ? b : -b;

        // 除法
        long res = div(a, b);
        if (sign > 0) {
            // 符号标志位位正数 结果大于最大值 返回最大值 否则直接返回
            return res > Integer.MAX_VALUE ? Integer.MAX_VALUE : res;
        }
        // 符号标志位位负数 返回相反数
        return -res;
    }

    private long div(long a, long b) {
        if (a < b) {
            // 如果被除数比除数还小 直接返回0
            return 0;
        }
        // 默认能被整除一次
        long count = 1;
        // 定义个临时除数
        long tempDivisor = b;
        // 除数翻倍还是小于被除数
        while ((tempDivisor + tempDivisor) <= a) {
            // 次数翻倍
            count = count + count;
            // 除数再次翻倍
            tempDivisor = tempDivisor + tempDivisor;
        }
        // 递归
        return count + div(a - tempDivisor, b);
    }

}
